package leetcode.每日一题;

import leetcode.util.CommonUtils;
import leetcode.剑指offer.pojo.TreeNode;
import org.junit.Test;

/**
 * @author ：zsy
 * @date ：Created 2022/11/9 11:00 PM
 * @description：
 */
public class 删除二叉搜索树中的节点 {
    @Test
    public void test() {
        new Solution().deleteNode(new TreeNode(50, new TreeNode(30, null, new TreeNode(40)), new TreeNode(70, new TreeNode(60), new TreeNode(80))), 50);
    }

    class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            TreeNode pre = null;
            TreeNode tmp = root;
            while (tmp != null) {
                if (tmp.val == key) break;
                pre = tmp;
                if (tmp.val > key) {
                    tmp = tmp.left;
                } else {
                    tmp = tmp.right;
                }
            }
            // 删除节点
            if (tmp != null) {
                // 右边最小的
                if (tmp.right != null) {
                    TreeNode rightTmp = tmp.right;
                    TreeNode leftPrev = null;
                    while (rightTmp.left != null) {
                        leftPrev = rightTmp;
                        rightTmp = rightTmp.left;
                    }
                    if (leftPrev != null) {
                        leftPrev.left = rightTmp.right;
                    }
                    rightTmp.left = tmp.left;
                    if (pre == null) {
                        root = rightTmp;
                    } else {
                        if (pre.left != null && pre.left.val == key) {
                            pre.left = rightTmp;
                        } else {
                            pre.right = rightTmp;
                        }
                    }
                } else { // 没有右节点
                    if (pre == null) {
                        root = tmp.left;
                    } else {
                        if (pre.left != null && pre.left.val == key) {
                            pre.left = tmp.left;
                        } else {
                            pre.right = tmp.left;
                        }
                    }
                }
            }
            return root;
        }
    }
}
